package unit13_动态规划.part3_大厂冲刺题;

public class LongestCommonSubsequence {

    public int longestCommonSubsequence(String A, String B) {
        int m = A.length();
        int n = B.length();
        int i, j;
        int[][] f = new int[2][n + 1];
        int old, now = 0;
        for (i = 0; i <= n; i++) {
            f[now][i] = 0;
        }
        for (i = 1; i <= m; i++) {
            old = now;
            now = 1 - now;
            for (j = 0; j <= n; j++) {
                f[now][j] = f[old][j];
                if (j > 0) {
                    f[now][j] = Math.max(f[now][j], f[now][j - 1]);
                }
                if (j > 0 && A.charAt(i - 1) == B.charAt(j - 1)) {
                    f[now][j] = Math.max(f[now][j], f[old][j - 1] + 1);
                }
            }
        }
        return f[now][n];
    }
}
